我們來練習幾題動態規劃的題目，就先從經典的最長遞增子序列開始．最長遞增子序列，Longest Increasing Subsequence，簡稱LIS，比較容易想到的是動態規劃解法，時間複雜度是n^2，而比較難想到的是使用二分搜尋，時間複雜度是nLogn

先來看題目

輸入一個”無序”的整數陣列．請從其中找出最長的遞增子序列

例如，輸入nums = [10,9,2,5,3,7,101,18]，其中最長的遞增子序列是[2,3,7,101]，所以輸出是4

子序列跟昨天提到的子字串不同，中間是可以斷開的，而子字串一定要連續

動態規劃解法

先將題目將低一點難度，nums = [1,4,2,4,2,3]

我們使用數學歸納法來思考

假設結論在k<n時成立，再證明在k=n時也成立，如果兩條都可行，則代表k=任何數都能成立

同樣的動態規劃

假設有一個dp陣列，其dp[0,1,2….i-1]都是成立，那怎麼透過這個前提算出dp[i]

以這題來說 ，dp矩陣就定義成dp[i] = nums[i]為結尾的最長遞增子序列的長度

根據這個定義可以得到base case 的dp[i] = 1，因為不管怎樣子序列都要包含自己這個起始點

nums[0]的最長遞增子序列為 [1] ，因此dp[0] =1

nums[1]的最長遞增子序列為 [1,4] ，因此dp[1] =2

nums[2]的最長遞增子序列為 [1,2] ，因此dp[2] =2

nums[3]的最長遞增子序列為 [1,2,4] ，因此dp[3] =3

nums[4]的最長遞增子序列為 [1,4] ，因此dp[4] =2

根據這個定義，最終結果，也就是子序列的最大長度，應該就是dp陣列中的最大值

var res = 0
    for(i in 0..dp.size){
        res = Math.max(res,dp[i])
    }
return res

好的，接下來進入重頭戲，如何藉由前面幾個結果，推導出後面的結果呢，也就是怎麼寫出狀態轉移方程

以這題為例子，我們已經有了dp[0],dp[1]．．．dp[4]了，如何推出dp[5]呢？

既然nums[5] = 3，既然是遞增子序列，也就是只要找出前面的答案中，最尾巴的答案比3小的就可以接上nums[5]，形成一個新的遞增子序列

但是以這題來說，最後一位小於3的有兩個，分別是nums[0]跟nums[2]時的最長遞增子序列．那麼我們從中選出比較長的那個來串上，也就是nums[2]

好的，我們有狀態轉移的方程式了，該來動手寫寫看了

fun lengthOfLIS(nums: Array<Int>):Int{
    val dp =  IntArray(nums.size){1}//base case :dp陣列全部初始化成1
    for(i in nums.indices){
        for(j in 0 until i){
            if(nums[i] > nums[j]){
                dp[i] = Math.max(dp[i],dp[j]+1)
            }
        }
    }
    var ans = 0
    //從新尋返一次dp陣列，找到其中最長的
    for(element in dp){
        ans = Math.max(ans, element)
    }
    return ans
}

因為用了兩層迴圈，所以時間複雜度是n^2

總結一下，有兩個小技巧

1.要好好確認dp列裡面存放的資料的含義，不管什麼動態規劃問題都很重要．

2.根據dp陣列的資料定義，利用數學歸納法的概念，假設已知dp[0,1….i-1]，則如何去推導出dp[i]

一但解決這兩個點，距離解決問題也不遠了．